//邻接表----C语言
#include <stdio.h>
#include <stdlib.h>

typedef struct EdgeNode{
    int vertex;  //表示边的结尾顶点
    int weight;  //表示边的权重
    struct EdgeNode *next; //指向下一个边结点
}EdgeNode;

typedef struct VertexNode{
    int vertex;  //顶点的索引
    EdgeNode *firstEdge;  //指向该结点的第一个边结点
}VertexNode;

typedef struct{
    int vertices;  //图的顶点数量
    VertexNode* nodes;  //指向一个VertexNode数组，用于储存图的顶点信息
}Graph;

//邻接表的创建
void GraphCreate(Graph* g,int vertices)
{
    g->vertices=vertices;
    g->nodes=(VertexNode*)malloc(sizeof(VertexNode)*vertices);
    for(int i=0;i<vertices;i++)
    {
        g->nodes[i].vertex=i;
        g->nodes[i].firstEdge=NULL;  //链表头
    }
}

//邻接表的销毁
void GraphDestroy(Graph *g)
{
    for(int i=0;i<g->vertices;i++)
    {
        EdgeNode* curr=g->nodes[i].firstEdge;
        while(curr)
        {
            EdgeNode* temp=curr;
            curr=curr->next;
            free(temp);
        }
    }
    free(g->nodes);
    g->nodes=NULL;
}

//邻接表的边添加
void GraphAddEdge(Graph* g,int u,int v,int w)
{
    EdgeNode* newNode=(EdgeNode* )malloc(sizeof(EdgeNode));
    newNode->vertex=v;
    newNode->weight=w;
    //头插法
    newNode->next=g->nodes[u].firstEdge;
    g->nodes[u].firstEdge=newNode;
}

//邻接表的打印
void GraphPrint(Graph* g)
{
    for(int i=0;i<g->vertices;i++)
    {
        EdgeNode* curr=g->nodes[i].firstEdge;
        printf("Vertex %d:",i);
        while(curr)
        {
            printf("%d(%d) ",curr->vertex,curr->weight);
            curr=curr->next;
        }
        printf("\n");
    }
}

int main()
{
    Graph g;
    GraphCreate(&g,5);
    GraphAddEdge(&g,0,1,4);
    GraphAddEdge(&g,0,2,2);
    GraphAddEdge(&g,1,2,3);
    GraphAddEdge(&g,2,3,4);
    GraphAddEdge(&g,3,4,2);
    GraphPrint(&g);
    GraphDestroy(&g);

    return 0;
}